package xyf.p10.dp;

import commons.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * ClassName: P0437_PathSum3
 * Description:
 * Author: xyf
 * Date: 9/9/22 10:30 AM
 * Version: 1.0
 **/
public class P0437_PathSum3
{
    private int count = 0;

    public int pathSum(TreeNode root, int targetSum)
    {
        dfs(root, targetSum);
        return count;
    }

    private Map<Long, Integer> dfs(TreeNode root, int targetSum)
    {
        if (root == null)
        {
            return new HashMap<>();
        }

        Map<Long, Integer> leftMap = dfs(root.left, targetSum);
        Map<Long, Integer> rightMap = dfs(root.right, targetSum);

        Map<Long, Integer> res = new HashMap<>();
        res.put((long) root.val, 1);
        for (Map.Entry<Long, Integer> entry : leftMap.entrySet())
        {
            Long key = entry.getKey() + root.val;
            Integer value = entry.getValue();
            Integer oldValue = res.getOrDefault(key, 0);
            value += oldValue;

            res.put(key, value);
        }

        for (Map.Entry<Long, Integer> entry : rightMap.entrySet())
        {
            Long key = entry.getKey() + root.val;
            Integer value = entry.getValue();
            Integer oldValue = res.getOrDefault(key, 0);
            value += oldValue;

            res.put(key, value);
        }

        for (Map.Entry<Long, Integer> entry : res.entrySet())
        {
            Long key = entry.getKey();
            if (key == targetSum)
            {
                count += entry.getValue();
            }
        }
        return res;
    }
}